//实现 strStr() 函数。 
//
// 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如
//果不存在，则返回 -1。 
//
// 示例 1: 
//
// 输入: haystack = "hello", needle = "ll"
//输出: 2
// 
//
// 示例 2: 
//
// 输入: haystack = "aaaaa", needle = "bba"
//输出: -1
// 
//
// 说明: 
//
// 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 
//
// 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。 
// Related Topics 双指针 字符串 
// 👍 535 👎 0

package leetcode.editor.cn;

//Java：实现 strStr()
public class P28ImplementStrstr {

    /**
     *   思路： 土方法一个一个判断
     *
     * 		执行耗时:6 ms,击败了18.31% 的Java用户
     * 		内存消耗:38.3 MB,击败了65.22% 的Java用户
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int strStr(String haystack, String needle) {
            if ("".equals(needle)) {
                return 0;
            }
            int result = -1;

            int k = -1;
            int i = 0;
            while (i < haystack.length()) {
                k++;
                if (k >= needle.length()) {
                    break;
                }
                if (haystack.charAt(i) != needle.charAt(k)) {
                    k = -1;
                    i = result == -1 ? i + 1 : result + 1;
                    result = -1;
                    continue;
                }
                if (result == -1) {
                    result = i;
                }
                i++;
            }
            if (k < needle.length() - 1) {
                return -1;
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P28ImplementStrstr().new Solution();
        System.out.println(solution.strStr("mississippi", "pi"));
        // TO TEST
    }

}